The invention relates to label switching, and more particularly to a method and system for preventing transmission loops between a group of network nodes that are connected to form a ring.
In packet-switched networks, packets traveling from a source address to a destination address may be transmitted through many intermediate network nodes, such as switches or routers. Intermediate network nodes that receive packets headed for the destination address utilize look-up tables to determine where the packets should be forwarded next. If an intermediate network node is familiar with the destination address of the packets, the packets are forwarded to the appropriate next hop. However, if the destination address of the packets is unknown to the network node, the network node may forward the incoming packets onto all of its ports, except for the port at which the packets were received, in order to deliver the packet to the unknown destination address. This technique for locating an unknown destination address, referred to as xe2x80x9cflooding,xe2x80x9d is repeated at each network node that is unfamiliar with the destination address of the packets until the packets eventually reach their destination or a network node that is familiar with the destination address of the packets. Return packets are then transmitted from the destination to the source through the intermediate network nodes. Once one of the packets is received by an intermediate network node, information regarding the destination address of the packet is learned by the intermediate network nodes so that subsequent packets do not have to be flooded. Although flooding works well to learn an unknown destination address, in mesh and ring network topologies, flooding at each network node often causes transmission loops that can quickly multiply and overwhelm a network node, causing traffic delays and network crashes. The occurrence of transmission loops is also a problem with multicast and broadcast packet transmissions.
One technique that is used at the Data Link layer (layer 2) to prevent transmission loops in a group of network nodes involves breaking the network topology down into a loop-free topology, also referred to as a spanning tree. A spanning tree protocol (STP) for determining, establishing, and maintaining a loop-free topology that includes every reachable link in a given network has been standardized by the Institute of Electrical and Electronics Engineers (IEEE) as IEEE 802.1D. The STP involves determining a Root Bridge, determining the Designated Bridges and Designated Ports for each link, and maintaining the spanning tree topology over time. Although the Spanning Tree Protocol works well to create loop-free topologies, establishing and maintaining the spanning tree is a cumbersome and resource intensive process.
As described above, packets traveling from a source address to a destination address may be transmitted through many intermediate network nodes. Performing forwarding look-ups at the intermediate network nodes based on the destination address of each packet adds delay to the packets. Label switching is a technique that has been developed to expedite the look-up process at each hop as packets travel from a source address to a destination address. In brief, label switching involves attaching a label to a packet that enables the next hop of the packet to be quickly determined by an intermediate network node that has received the packet. One label switching protocol that is being standardized by the Internet Engineering Task Force (IETF) is known as multi-protocol label switching (MPLS).
FIG. 1 depicts a group of network nodes 102 that utilize MPLS to forward packets. The network nodes are referred to as label switch routers (LSRs) and a group of interconnected LSRs define an MPLS domain 104. LSRs that are at the edge of the MPLS domain and provide an interface to non-MPLS network nodes are referred to as edge LSRs (also as ingress LSRs and egress LSRs with respect to packets that are entering or leaving the MPLS domain). The path that labeled packets travel through an MPLS domain is referred to as the label switch path (LSP). FIG. 1 depicts an example LSP 106 that extends through the MPLS domain. MPLS is often used in conjunction with the Internet protocol (IP) at the Network layer (layer 3) and a Data Link layer (layer 2) protocol such as the Ethernet protocol (IEEE 802.3x). According to the MPLS protocol, an MPLS label, also referred to as a xe2x80x9cshim header,xe2x80x9d is inserted between the Network layer header and the Data Link layer header to guide a labeled packet through an MPLS domain. MPLS can also be used in a layer 2 environment where the shim header is located between two layer 2 headers.
FIG. 2 depicts an example of a labeled packet that includes a MAC (Data Link layer or layer 2) header 208 (the destination address, the source address, and the type), a label switching header 210 (also referred to as the shim header), an IP header 212, an IP payload 214, and a MAC trailer 216 (the CRC). As described by the IETF (RFC 3032, January 2001) and shown in the expanded view of FIG. 2, the shim header includes a 20-bit MPLS label field 218, a 3-bit experimental use field 220, a 1-bit stacking field 222, and an 8-bit time-to-live (TTL) field 224. The MPLS label field carries the label value that is used to forward a packet to the next LSR. The experimental use field is not yet fully defined, the stacking field is used to identify when an MPLS header is the last MPLS header in a stack of MPLS headers, and the TTL field carries a TTL value that places a limit on the number of hops an MPLS packet can traverse within an MPLS domain. The TTL field limits the number of hops a packet can take within an MPLS domain. Typically, in an IP environment, the TTL value of an MPLS label is initially set from the TTL value of the underlying IP packet and the IP packet TTL value is typically set by a host to an arbitrary number of hops. Although MPLS can increase transmission efficiency in an MPLS network, setting the TTL value in the MPLS Shim header to the TTL value of the underlying IP packet does not prevent loops within an MPLS domain. Additionally, in a layer 2 environment, the underlying MAC header does not include a TTL value that can be used to set the TTL value in the MPLS shim header.
In view of the problems caused by flooding, multicasting, and broadcasting, what is needed is a technique that prevents transmission loops and that is compatible with a label switching protocol such as MPLS.
A method and system for preventing transmission loops in a ring network that utilizes label switching involves generating right side and left side ring packets from an ingress packet and setting right and left TTL values for the packets that prevent the packets from traveling on the same transmission link. Setting the right and left TTL values of the ring packets to values that prevent the packets from traveling on the same link transforms the physical topology of a ring into a logical arc. In an embodiment, the logical arc established by a network node can be dynamically rotated to avoid packet transmissions on a particular link of the ring network.
In an embodiment, a method for preventing transmission loops is implemented between a plurality of network nodes that are connected by transmission links to form a ring, wherein each network node on the ring includes a right side ringport that is connected to a right side neighbor and a left side ringport that is connected to a left side neighbor and wherein each of the network nodes in the ring utilizes a label switching protocol that includes a label, the label including a label field for carrying a label value and a time-to-live (TTL) field for carrying a TTL value. The method involves generating, at a first one of the plurality of network nodes, a right side packet and a left side packet from an ingress packet and setting a right side TTL value for the right side packet and a left side TTL value for the left side packet to values that prevent the right side packet and the left side packet from traveling on the same transmission link on the ring.
An embodiment of the method includes learning the number (N) of network nodes on the ring. A further embodiment includes setting the right side TTL value and the left side TTL value to values that are a function of N. A further embodiment includes setting the right side TTL value and the left side TTL value such that the maximum number of right side hops (MaxRightHops) plus the maximum number of left side hops (MaxLeftHops) is less than or equal to Nxe2x88x921, the function of N being expressed as: MaxRightHops+MaxLeftHopsxe2x89xa6Nxe2x88x921.
Another embodiment of the method includes setting the right side TTL value and the left side TTL value such that the number of hops for the right side packet is equal to the number hops for the left side packet.
Another embodiment of the method includes setting the right side TTL value and the left side TTL value such that the number of hops for the right side packet differs from the number hops for the left side packet by one hop.
Another embodiment of the method includes setting the right side TTL value and the left side TTL value such that the furthest transmission link from the first network node is a transmission link that is not utilized by either the right side packet or left side packet.
Another embodiment of the method includes setting the right side TTL value and the left side TTL value in response to link performance information related to the transmission links that connect the network nodes into the ring.
Another embodiment of the method includes dynamically adjusting the right side and left side TTL values.
Another embodiment of the method involves transmitting the right side packet on the right side ringport of the first network node and the left side packet on the left side ringport of the first network node. A further embodiment includes decrementing the right side TTL value of the right side packet at each network node on the ring that receives the right side packet and the left side TTL value of the left side packet at each network node on the ring that receives the left side packet.
In an embodiment of the method, the label is located between two Data Link layer headers.
In an embodiment of the method, the network nodes utilize Ethernet at the Data Link layer.
In an embodiment of the method, the label is a Multiprotocol Label Switching (MPLS) header. In a further embodiment, the method includes establishing, at the first network node, multiple label switch paths that have different quality of service characteristics and setting the same right side TTL values and left side TTL values for all packets transmitted on the multiple LSPs.
In another embodiment, a method for preventing transmission loops is implemented between a plurality of network nodes that are connected by transmission links to form a ring, wherein each network node on the ring includes a right side ringport that is connected to a right side neighbor and a left side ringport that is connected to a left side neighbor and wherein each of the network nodes in the ring utilizes a label switching protocol that includes a label, the label including a label field for carrying a label value and a time-to-live (TTL) field for carrying a TTL value. The method involves learning, at a first one of the plurality of network nodes, the number (N) of network nodes on the ring, generating, at the first network node, a right side packet and a left side packet from an ingress packet, and setting a right side TTL value for the right side packet and a left side TTL value for the left side packet to values that are a function of N.
An embodiment of the method includes setting the right side TTL value and the left side TTL value to values that prevent the right side packet and the left side packet from traveling on the same transmission link on the ring.
Another embodiment of the method includes setting the right side TTL value and the left side TTL value such that the maximum number of right side hops (MaxRightHops) plus the maximum number of left side hops (MaxLeftHops) is less than or equal to Nxe2x88x921, the function of N being expressed as MaxRightHops+MaxLeftHopsxe2x89xa6Nxe2x88x921.
An embodiment of a system for preventing transmission loops in a ring network includes a plurality of network nodes, with each network node including a right side ringport, a left side ringport, a packet processor, and a loop protection module. The network nodes are connected by transmission links to form a ring, wherein each of the network nodes on the ring utilizes a label switching protocol that includes a label, the label including a label field for carrying a label value and a time-to-live (TTL) field for carrying a TTL value. The right side ringport of each network node is connected to a right side neighbor and the left side ringport is connected to a left side neighbor. The packet processor of each network node generates a right side packet and a left side packet from an ingress packet and the loop protection module sets a right side TTL value for the right side packet and a left side TTL value for the left side packet to values that prevent the right side packet and the left side packet from traveling on the same transmission link on the ring.
Another embodiment of a system for preventing transmission loops in a ring network includes a plurality of network nodes, with each network node including a right side ringport, a left side ringport, a packet processor, and a loop protection module. The network nodes are connected by transmission links to form a ring, wherein each of the network nodes on the ring utilizes a label switching protocol that includes a label, the label including a label field for carrying a label value and a time-to-live (TTL) field for carrying a TTL value. The right side ringport of each network node is connected to a right side neighbor and the left side ringport is connected to a left side neighbor. The packet processor of each network node generates a right side packet and a left side packet from an ingress packet. The loop protection module learns the number (N) of network nodes on the ring and sets a right side TTL value for the right side packet and a left side TTL value for the left side packet to values that are a function of N.
In an embodiment of the system, the right side TTL value and the left side TTL value are set such that the maximum number of right side hops (MaxRightHops) plus the maximum number of left side hops (MaxLeftHops) is less than or equal to Nxe2x88x921, the function of N being expressed as MaxRightHops+MaxLeftHopsxe2x89xa6Nxe2x88x921.
Other aspects and advantages of the present invention will become apparent from the following detailed description, taken in conjunction with the accompanying drawings, illustrating by way of example the principles of the invention.